/**
 * @author VernHe
 * @date 2021年10月29日 9:27
 */
public class Solution_0543 {
    public int diameterOfBinaryTree(TreeNode root) {
        int[] result = searchDiameter(root);
        return result[0];
    }

    /**
     * 后序遍历查找直径
     * @param node  当前节点
     * @return  [以当前节点为根节点时的最大直径，当前节点作为子节点时最长的一条路径]
     */
    private int[] searchDiameter(TreeNode node) {
        if (node == null) {
            return new int[]{0,0};
        }
        int[] leftVal = new int[]{0,0};
        if (null != node.left) {
            leftVal = searchDiameter(node.left);
        }
        int[] rightVal = new int[]{0,0};
        if (null != node.right) {
            rightVal = searchDiameter(node.right);
        }
        // 组合后的直径
        int sum = leftVal[1] + rightVal[1];
        // 子节点的最大直径
        int maxDiameter = Math.max(leftVal[0], rightVal[0]);
        return new int[]{Math.max(sum,maxDiameter), Math.max(leftVal[1], rightVal[1]) + 1};
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        System.out.println(new Solution_0543().diameterOfBinaryTree(root));
    }
}
